<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 8.6.7" />
<title>uthash User Guide</title>
<style type="text/css">
/* Shared CSS for AsciiDoc xhtml11 and html5 backends */

/* Default font. */
body {
  font-family: Georgia,serif;
}

/* Title font. */
h1, h2, h3, h4, h5, h6,
div.title, caption.title,
thead, p.table.header,
#toctitle,
#author, #revnumber, #revdate, #revremark,
#footer {
  font-family: Arial,Helvetica,sans-serif;
}

body {
  margin: 1em 5% 1em 5%;
}

a {
  color: blue;
  text-decoration: underline;
}
a:visited {
  color: fuchsia;
}

em {
  font-style: italic;
  color: navy;
}

strong {
  font-weight: bold;
  color: #083194;
}

h1, h2, h3, h4, h5, h6 {
  color: #527bbd;
  margin-top: 1.2em;
  margin-bottom: 0.5em;
  line-height: 1.3;
}

h1, h2, h3 {
  border-bottom: 2px solid silver;
}
h2 {
  padding-top: 0.5em;
}
h3 {
  float: left;
}
h3 + * {
  clear: left;
}
h5 {
  font-size: 1.0em;
}

div.sectionbody {
  margin-left: 0;
}

hr {
  border: 1px solid silver;
}

p {
  margin-top: 0.5em;
  margin-bottom: 0.5em;
}

ul, ol, li > p {
  margin-top: 0;
}
ul > li     { color: #aaa; }
ul > li > * { color: black; }

pre {
  padding: 0;
  margin: 0;
}

#author {
  color: #527bbd;
  font-weight: bold;
  font-size: 1.1em;
}
#email {
}
#revnumber, #revdate, #revremark {
}

#footer {
  font-size: small;
  border-top: 2px solid silver;
  padding-top: 0.5em;
  margin-top: 4.0em;
}
#footer-text {
  float: left;
  padding-bottom: 0.5em;
}
#footer-badges {
  float: right;
  padding-bottom: 0.5em;
}

#preamble {
  margin-top: 1.5em;
  margin-bottom: 1.5em;
}
div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.admonitionblock {
  margin-top: 2.0em;
  margin-bottom: 2.0em;
  margin-right: 10%;
  color: #606060;
}

div.content { /* Block element content. */
  padding: 0;
}

/* Block element titles. */
div.title, caption.title {
  color: #527bbd;
  font-weight: bold;
  text-align: left;
  margin-top: 1.0em;
  margin-bottom: 0.5em;
}
div.title + * {
  margin-top: 0;
}

td div.title:first-child {
  margin-top: 0.0em;
}
div.content div.title:first-child {
  margin-top: 0.0em;
}
div.content + div.title {
  margin-top: 0.0em;
}

div.sidebarblock > div.content {
  background: #ffffee;
  border: 1px solid #dddddd;
  border-left: 4px solid #f0f0f0;
  padding: 0.5em;
}

div.listingblock > div.content {
  border: 1px solid #dddddd;
  border-left: 5px solid #f0f0f0;
  background: #f8f8f8;
  padding: 0.5em;
}

div.quoteblock, div.verseblock {
  padding-left: 1.0em;
  margin-left: 1.0em;
  margin-right: 10%;
  border-left: 5px solid #f0f0f0;
  color: #888;
}

div.quoteblock > div.attribution {
  padding-top: 0.5em;
  text-align: right;
}

div.verseblock > pre.content {
  font-family: inherit;
  font-size: inherit;
}
div.verseblock > div.attribution {
  padding-top: 0.75em;
  text-align: left;
}
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
div.verseblock + div.attribution {
  text-align: left;
}

div.admonitionblock .icon {
  vertical-align: top;
  font-size: 1.1em;
  font-weight: bold;
  text-decoration: underline;
  color: #527bbd;
  padding-right: 0.5em;
}
div.admonitionblock td.content {
  padding-left: 0.5em;
  border-left: 3px solid #dddddd;
}

div.exampleblock > div.content {
  border-left: 3px solid #dddddd;
  padding-left: 0.5em;
}

div.imageblock div.content { padding-left: 0; }
span.image img { border-style: none; }
a.image:visited { color: white; }

dl {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
dt {
  margin-top: 0.5em;
  margin-bottom: 0;
  font-style: normal;
  color: navy;
}
dd > *:first-child {
  margin-top: 0.1em;
}

ul, ol {
    list-style-position: outside;
}
ol.arabic {
  list-style-type: decimal;
}
ol.loweralpha {
  list-style-type: lower-alpha;
}
ol.upperalpha {
  list-style-type: upper-alpha;
}
ol.lowerroman {
  list-style-type: lower-roman;
}
ol.upperroman {
  list-style-type: upper-roman;
}

div.compact ul, div.compact ol,
div.compact p, div.compact p,
div.compact div, div.compact div {
  margin-top: 0.1em;
  margin-bottom: 0.1em;
}

tfoot {
  font-weight: bold;
}
td > div.verse {
  white-space: pre;
}

div.hdlist {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
div.hdlist tr {
  padding-bottom: 15px;
}
dt.hdlist1.strong, td.hdlist1.strong {
  font-weight: bold;
}
td.hdlist1 {
  vertical-align: top;
  font-style: normal;
  padding-right: 0.8em;
  color: navy;
}
td.hdlist2 {
  vertical-align: top;
}
div.hdlist.compact tr {
  margin: 0;
  padding-bottom: 0;
}

.comment {
  background: yellow;
}

.footnote, .footnoteref {
  font-size: 0.8em;
}

span.footnote, span.footnoteref {
  vertical-align: super;
}

#footnotes {
  margin: 20px 0 20px 0;
  padding: 7px 0 0 0;
}

#footnotes div.footnote {
  margin: 0 0 5px 0;
}

#footnotes hr {
  border: none;
  border-top: 1px solid silver;
  height: 1px;
  text-align: left;
  margin-left: 0;
  width: 20%;
  min-width: 100px;
}

div.colist td {
  padding-right: 0.5em;
  padding-bottom: 0.3em;
  vertical-align: top;
}
div.colist td img {
  margin-top: 0.3em;
}

@media print {
  #footer-badges { display: none; }
}

#toc {
  margin-bottom: 2.5em;
}

#toctitle {
  color: #527bbd;
  font-size: 1.1em;
  font-weight: bold;
  margin-top: 1.0em;
  margin-bottom: 0.1em;
}

div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
  margin-top: 0;
  margin-bottom: 0;
}
div.toclevel2 {
  margin-left: 2em;
  font-size: 0.9em;
}
div.toclevel3 {
  margin-left: 4em;
  font-size: 0.9em;
}
div.toclevel4 {
  margin-left: 6em;
  font-size: 0.9em;
}

span.aqua { color: aqua; }
span.black { color: black; }
span.blue { color: blue; }
span.fuchsia { color: fuchsia; }
span.gray { color: gray; }
span.green { color: green; }
span.lime { color: lime; }
span.maroon { color: maroon; }
span.navy { color: navy; }
span.olive { color: olive; }
span.purple { color: purple; }
span.red { color: red; }
span.silver { color: silver; }
span.teal { color: teal; }
span.white { color: white; }
span.yellow { color: yellow; }

span.aqua-background { background: aqua; }
span.black-background { background: black; }
span.blue-background { background: blue; }
span.fuchsia-background { background: fuchsia; }
span.gray-background { background: gray; }
span.green-background { background: green; }
span.lime-background { background: lime; }
span.maroon-background { background: maroon; }
span.navy-background { background: navy; }
span.olive-background { background: olive; }
span.purple-background { background: purple; }
span.red-background { background: red; }
span.silver-background { background: silver; }
span.teal-background { background: teal; }
span.white-background { background: white; }
span.yellow-background { background: yellow; }

span.big { font-size: 2em; }
span.small { font-size: 0.6em; }

span.underline { text-decoration: underline; }
span.overline { text-decoration: overline; }
span.line-through { text-decoration: line-through; }

div.unbreakable { page-break-inside: avoid; }


/*
 * xhtml11 specific
 *
 * */

tt {
  font-family: "Courier New", Courier, monospace;
  font-size: inherit;
  color: navy;
}

div.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.tableblock > table {
  border: 3px solid #527bbd;
}
thead, p.table.header {
  font-weight: bold;
  color: #527bbd;
}
p.table {
  margin-top: 0;
}
/* Because the table frame attribute is overriden by CSS in most browsers. */
div.tableblock > table[frame="void"] {
  border-style: none;
}
div.tableblock > table[frame="hsides"] {
  border-left-style: none;
  border-right-style: none;
}
div.tableblock > table[frame="vsides"] {
  border-top-style: none;
  border-bottom-style: none;
}


/*
 * html5 specific
 *
 * */

.monospaced {
  font-family: "Courier New", Courier, monospace;
  font-size: inherit;
  color: navy;
}

table.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
thead, p.tableblock.header {
  font-weight: bold;
  color: #527bbd;
}
p.tableblock {
  margin-top: 0;
}
table.tableblock {
  border-width: 3px;
  border-spacing: 0px;
  border-style: solid;
  border-color: #527bbd;
  border-collapse: collapse;
}
th.tableblock, td.tableblock {
  border-width: 1px;
  padding: 4px;
  border-style: solid;
  border-color: #527bbd;
}

table.tableblock.frame-topbot {
  border-left-style: hidden;
  border-right-style: hidden;
}
table.tableblock.frame-sides {
  border-top-style: hidden;
  border-bottom-style: hidden;
}
table.tableblock.frame-none {
  border-style: hidden;
}

th.tableblock.halign-left, td.tableblock.halign-left {
  text-align: left;
}
th.tableblock.halign-center, td.tableblock.halign-center {
  text-align: center;
}
th.tableblock.halign-right, td.tableblock.halign-right {
  text-align: right;
}

th.tableblock.valign-top, td.tableblock.valign-top {
  vertical-align: top;
}
th.tableblock.valign-middle, td.tableblock.valign-middle {
  vertical-align: middle;
}
th.tableblock.valign-bottom, td.tableblock.valign-bottom {
  vertical-align: bottom;
}


/*
 * manpage specific
 *
 * */

body.manpage h1 {
  padding-top: 0.5em;
  padding-bottom: 0.5em;
  border-top: 2px solid silver;
  border-bottom: 2px solid silver;
}
body.manpage h2 {
  border-style: none;
}
body.manpage div.sectionbody {
  margin-left: 3em;
}

@media print {
  body.manpage div#toc { display: none; }
}
@media screen {
  body {
    max-width: 50em; /* approximately 80 characters wide */
    margin-left: 16em;
  }

  #toc {
    position: fixed;
    top: 0;
    left: 0;
    bottom: 0;
    width: 13em;
    padding: 0.5em;
    padding-bottom: 1.5em;
    margin: 0;
    overflow: auto;
    border-right: 3px solid #f8f8f8;
    background-color: white;
  }

  #toc .toclevel1 {
    margin-top: 0.5em;
  }

  #toc .toclevel2 {
    margin-top: 0.25em;
    display: list-item;
    color: #aaaaaa;
  }

  #toctitle {
    margin-top: 0.5em;
  }
}
</style>
<script type="text/javascript">
/*<![CDATA[*/
var asciidoc = {  // Namespace.

/////////////////////////////////////////////////////////////////////
// Table Of Contents generator
/////////////////////////////////////////////////////////////////////

/* Author: Mihai Bazon, September 2002
 * http://students.infoiasi.ro/~mishoo
 *
 * Table Of Content generator
 * Version: 0.4
 *
 * Feel free to use this script under the terms of the GNU General Public
 * License, as long as you do not remove or alter this notice.
 */

 /* modified by Troy D. Hanson, September 2006. License: GPL */
 /* modified by Stuart Rackham, 2006, 2009. License: GPL */

// toclevels = 1..4.
toc: function (toclevels) {

  function getText(el) {
    var text = "";
    for (var i = el.firstChild; i != null; i = i.nextSibling) {
      if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
        text += i.data;
      else if (i.firstChild != null)
        text += getText(i);
    }
    return text;
  }

  function TocEntry(el, text, toclevel) {
    this.element = el;
    this.text = text;
    this.toclevel = toclevel;
  }

  function tocEntries(el, toclevels) {
    var result = new Array;
    var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
    // Function that scans the DOM tree for header elements (the DOM2
    // nodeIterator API would be a better technique but not supported by all
    // browsers).
    var iterate = function (el) {
      for (var i = el.firstChild; i != null; i = i.nextSibling) {
        if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
          var mo = re.exec(i.tagName);
          if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
            result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
          }
          iterate(i);
        }
      }
    }
    iterate(el);
    return result;
  }

  var toc = document.getElementById("toc");
  if (!toc) {
    return;
  }

  // Delete existing TOC entries in case we're reloading the TOC.
  var tocEntriesToRemove = [];
  var i;
  for (i = 0; i < toc.childNodes.length; i++) {
    var entry = toc.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div'
     && entry.getAttribute("class")
     && entry.getAttribute("class").match(/^toclevel/))
      tocEntriesToRemove.push(entry);
  }
  for (i = 0; i < tocEntriesToRemove.length; i++) {
    toc.removeChild(tocEntriesToRemove[i]);
  }

  // Rebuild TOC entries.
  var entries = tocEntries(document.getElementById("content"), toclevels);
  for (var i = 0; i < entries.length; ++i) {
    var entry = entries[i];
    if (entry.element.id == "")
      entry.element.id = "_toc_" + i;
    var a = document.createElement("a");
    a.href = "#" + entry.element.id;
    a.appendChild(document.createTextNode(entry.text));
    var div = document.createElement("div");
    div.appendChild(a);
    div.className = "toclevel" + entry.toclevel;
    toc.appendChild(div);
  }
  if (entries.length == 0)
    toc.parentNode.removeChild(toc);
},


/////////////////////////////////////////////////////////////////////
// Footnotes generator
/////////////////////////////////////////////////////////////////////

/* Based on footnote generation code from:
 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 */

footnotes: function () {
  // Delete existing footnote entries in case we're reloading the footnodes.
  var i;
  var noteholder = document.getElementById("footnotes");
  if (!noteholder) {
    return;
  }
  var entriesToRemove = [];
  for (i = 0; i < noteholder.childNodes.length; i++) {
    var entry = noteholder.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
      entriesToRemove.push(entry);
  }
  for (i = 0; i < entriesToRemove.length; i++) {
    noteholder.removeChild(entriesToRemove[i]);
  }

  // Rebuild footnote entries.
  var cont = document.getElementById("content");
  var spans = cont.getElementsByTagName("span");
  var refs = {};
  var n = 0;
  for (i=0; i<spans.length; i++) {
    if (spans[i].className == "footnote") {
      n++;
      var note = spans[i].getAttribute("data-note");
      if (!note) {
        // Use [\s\S] in place of . so multi-line matches work.
        // Because JavaScript has no s (dotall) regex flag.
        note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
        spans[i].innerHTML =
          "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
        spans[i].setAttribute("data-note", note);
      }
      noteholder.innerHTML +=
        "<div class='footnote' id='_footnote_" + n + "'>" +
        "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
        n + "</a>. " + note + "</div>";
      var id =spans[i].getAttribute("id");
      if (id != null) refs["#"+id] = n;
    }
  }
  if (n == 0)
    noteholder.parentNode.removeChild(noteholder);
  else {
    // Process footnoterefs.
    for (i=0; i<spans.length; i++) {
      if (spans[i].className == "footnoteref") {
        var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
        href = href.match(/#.*/)[0];  // Because IE return full URL.
        n = refs[href];
        spans[i].innerHTML =
          "[<a href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
      }
    }
  }
},

install: function(toclevels) {
  var timerId;

  function reinstall() {
    asciidoc.footnotes();
    if (toclevels) {
      asciidoc.toc(toclevels);
    }
  }

  function reinstallAndRemoveTimer() {
    clearInterval(timerId);
    reinstall();
  }

  timerId = setInterval(reinstall, 500);
  if (document.addEventListener)
    document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
  else
    window.onload = reinstallAndRemoveTimer;
}

}
asciidoc.install(2);
/*]]>*/
</script>
</head>
<body class="article">
<div id="header">
<h1>uthash User Guide</h1>
<span id="author">Troy D. Hanson</span><br />
<span id="email"><tt>&lt;<a href="mailto:tdh@tkhanson.net">tdh@tkhanson.net</a>&gt;</tt></span><br />
<span id="revnumber">version 1.9.8,</span>
<span id="revdate">March 2013</span>
<div id="toc">
  <div id="toctitle">Table of Contents</div>
  <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
</div>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>To download uthash, follow this link back to the
<a href="https://github.com/troydhanson/uthash">GitHub project page</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_a_hash_in_c">A hash in C</h2>
<div class="sectionbody">
<div class="paragraph"><p>This document is written for C programmers. Since you&#8217;re reading this, chances
are that you know a hash is used for looking up items using a key. In scripting
languages, hashes or "dictionaries" are used all the time.  In C, hashes don&#8217;t
exist in the language itself. This software provides a hash table for C
structures.</p></div>
<div class="sect2">
<h3 id="_what_can_it_do">What can it do?</h3>
<div class="paragraph"><p>This software supports these operations on items in a hash table:</p></div>
<div class="olist arabic"><ol class="arabic">
<li>
<p>
add/replace
</p>
</li>
<li>
<p>
find
</p>
</li>
<li>
<p>
delete
</p>
</li>
<li>
<p>
count
</p>
</li>
<li>
<p>
iterate
</p>
</li>
<li>
<p>
sort
</p>
</li>
<li>
<p>
select
</p>
</li>
</ol></div>
</div>
<div class="sect2">
<h3 id="_is_it_fast">Is it fast?</h3>
<div class="paragraph"><p>Add, find and delete are normally constant-time operations. This is influenced
by your key domain and the hash function.</p></div>
<div class="paragraph"><p>This hash aims to be minimalistic and efficient. It&#8217;s around 900 lines of C.
It inlines automatically because it&#8217;s implemented as macros. It&#8217;s fast as long
as the hash function is suited to your keys. You can use the default hash
function, or easily compare performance and choose from among several other
<a href="#hash_functions">built-in hash functions</a>.</p></div>
</div>
<div class="sect2">
<h3 id="_is_it_a_library">Is it a library?</h3>
<div class="paragraph"><p>No, it&#8217;s just a single header file: <tt>uthash.h</tt>.  All you need to do is copy
the header file into your project, and:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>#include "uthash.h"</tt></pre>
</div></div>
<div class="paragraph"><p>Since uthash is a header file only, there is no library code to link against.</p></div>
</div>
<div class="sect2">
<h3 id="_c_c_and_platforms">C/C++ and platforms</h3>
<div class="paragraph"><p>This software can be used in C and C++ programs.  It has been tested on:</p></div>
<div class="ulist"><ul>
<li>
<p>
Linux
</p>
</li>
<li>
<p>
Mac OS X
</p>
</li>
<li>
<p>
Windows using Visual Studio 2008 and 2010
</p>
</li>
<li>
<p>
Solaris
</p>
</li>
<li>
<p>
OpenBSD
</p>
</li>
<li>
<p>
FreeBSD
</p>
</li>
</ul></div>
<div class="paragraph"><p>Windows users: as of 2013 it&#8217;s been a while since I had the environment to test
uthash under Visual Studio. If someone wants to run the unit tests under the latest
Visual Studio and confirm that its still clean, that&#8217;d be appreciated.</p></div>
<div class="sect3">
<h4 id="_test_suite">Test suite</h4>
<div class="paragraph"><p>To run the test suite, enter the <tt>tests</tt> directory. Then,</p></div>
<div class="ulist"><ul>
<li>
<p>
on Unix platforms, run <tt>make</tt>
</p>
</li>
<li>
<p>
on Windows, run the "do_tests_win32.cmd" batch file. (You may edit the
   batch file if your Visual Studio is installed in a non-standard location).
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect2">
<h3 id="_bsd_licensed">BSD licensed</h3>
<div class="paragraph"><p>This software is made available under the
<a href="license.html">revised BSD license</a>.
It is free and open source.</p></div>
</div>
<div class="sect2">
<h3 id="_download_uthash">Download uthash</h3>
<div class="paragraph"><p>Follow the links on <a href="https://github.com/troydhanson/uthash">https://github.com/troydhanson/uthash</a> to clone uthash or get a zip file.</p></div>
</div>
<div class="sect2">
<h3 id="_getting_help">Getting help</h3>
<div class="paragraph"><p>I encourage people to use the public Google Group to ask questions: <a href="mailto:uthash@googlegroups.com">uthash@googlegroups.com</a></p></div>
<div class="paragraph"><p>You can browse it at: <a href="https://groups.google.com/d/forum/uthash">https://groups.google.com/d/forum/uthash</a></p></div>
<div class="paragraph"><p>If you are experienced with uthash and like to answer questions, please join the
group and chime in when someone asks a question. That would be a great help!</p></div>
<div class="sect3">
<h4 id="_contacting_the_author">Contacting the author</h4>
<div class="paragraph"><p>You can email me at <a href="mailto:tdh@tkhanson.net">tdh@tkhanson.net</a> or message @troydhanson on Twitter.  I
can&#8217;t always answer my email, and when I do, it&#8217;s sometimes weeks later. Sorry!</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_contributing">Contributing</h3>
<div class="paragraph"><p>If you add a new feature or fix something in uthash or in the extras, please
make a pull request on Github. For anything other than a trivial change, include
a unit test and documentation if you possibly can. (And don&#8217;t be discouraged if
it takes weeks or even months for me to merge it. Sorry, my life is busy!) Thanks!</p></div>
</div>
<div class="sect2">
<h3 id="_extras_included">Extras included</h3>
<div class="paragraph"><p>Three "extras" come with uthash. These provide lists, dynamic arrays and
strings:</p></div>
<div class="ulist"><ul>
<li>
<p>
<a href="utlist.html">utlist.h</a> provides linked list macros for C structures.
</p>
</li>
<li>
<p>
<a href="utarray.html">utarray.h</a> implements dynamic arrays using macros.
</p>
</li>
<li>
<p>
<a href="utstring.html">utstring.h</a> implements a basic dynamic string.
</p>
</li>
</ul></div>
<div class="paragraph"><p>There&#8217;s also a small LRU cache API, based on uthash, in <tt>tests/lru_cache</tt>.</p></div>
<div class="sect3">
<h4 id="_other_software">Other software</h4>
<div class="paragraph"><p>Other open-source software by the author is listed at <a href="http://tkhanson.net">http://tkhanson.net</a>.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_news">News</h3>
<div class="paragraph"><p>The author has a blog for <a href="http://troydhanson.wordpress.com/">software updates</a>
<span class="image">
<img src="rss.png" alt="(RSS)" />
</span>. You can also follow @troydhanson on Twitter for updates.</p></div>
</div>
<div class="sect2">
<h3 id="_who_8217_s_using_it">Who&#8217;s using it?</h3>
<div class="paragraph"><p>Uthash was downloaded around 30,000 times between 2006-2013 then transitioned to
GitHub. It&#8217;s been incorporated into commercial software, academic research, and
into other open-source software. It has also been added to the native package
repositories for a number of Unix-y distros.</p></div>
<div class="paragraph"><p>When uthash was written, there were fewer options for doing generic hash tables
in C than exist today. There are faster hash tables, more memory-efficient hash
tables, with very different API&#8217;s today. But, like driving a minivan, uthash is
convenient, and gets the job done without drawing a lot of attention to itself.</p></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_your_structure">Your structure</h2>
<div class="sectionbody">
<div class="paragraph"><p>In uthash, a hash table is comprised of structures. Each structure represents a
key-value association. One or more of the structure fields constitute the key.
The structure pointer itself is the value.</p></div>
<div class="listingblock">
<div class="title">Defining a structure that can be hashed</div>
<div class="content">
<pre><tt>#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};</tt></pre>
</div></div>
<div class="paragraph"><p>Note that, in uthash, your structure will never be moved or copied into another
location when you add it into a hash table. This means that you can keep other
data structures that safely point to your structure-- regardless of whether you
add or delete it from a hash table during your program&#8217;s lifetime.</p></div>
<div class="sect2">
<h3 id="_the_key">The key</h3>
<div class="paragraph"><p>There are no restrictions on the data type or name of the key field. The key
can also comprise multiple contiguous fields, having any names and data types.</p></div>
<div class="sidebarblock">
<div class="content">
<div class="title">Any data type&#8230; really?</div>
<div class="paragraph"><p>Yes, your key and structure can have any data type. Unlike function calls with
fixed prototypes, uthash consists of macros-- whose arguments are untyped-- and
thus able to work with any type of structure or key.</p></div>
</div></div>
<div class="sect3">
<h4 id="_unique_keys">Unique keys</h4>
<div class="paragraph"><p>As with any hash, every item must have a unique key.  Your application must
enforce key uniqueness. Before you add an item to the hash table, you must
first know (if in doubt, check!) that the key is not already in use.  You
can check whether a key already exists in the hash table using <tt>HASH_FIND</tt>.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_the_hash_handle">The hash handle</h3>
<div class="paragraph"><p>The <tt>UT_hash_handle</tt> field must be present in your structure.  It is used for
the internal bookkeeping that makes the hash work.  It does not require
initialization. It can be named anything, but you can simplify matters by
naming it <tt>hh</tt>. This allows you to use the easier "convenience" macros to add,
find and delete items.</p></div>
</div>
<div class="sect2">
<h3 id="_a_word_about_memory">A word about memory</h3>
<div class="sect3">
<h4 id="_overhead">Overhead</h4>
<div class="paragraph"><p>The hash handle consumes about 32 bytes per item on a 32-bit system, or 56 bytes
per item on a 64-bit system. The other overhead costs-- the buckets and the
table-- are negligible in comparison. You can use <tt>HASH_OVERHEAD</tt> to get the
overhead size, in bytes, for a hash table. See <a href="#Macro_reference">Macro Reference</a>.</p></div>
</div>
<div class="sect3">
<h4 id="_how_clean_up_occurs">How clean up occurs</h4>
<div class="paragraph"><p>Some have asked how uthash cleans up its internal memory. The answer is simple:
<em>when you delete the final item</em> from a hash table, uthash releases all the
internal memory associated with that hash table, and sets its pointer to NULL.</p></div>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_hash_operations">Hash operations</h2>
<div class="sectionbody">
<div class="paragraph"><p>This section introduces the uthash macros by example. For a more succinct
listing, see <a href="#Macro_reference">Macro Reference</a>.</p></div>
<div class="sidebarblock">
<div class="content">
<div class="title">Convenience vs. general macros:</div>
<div class="paragraph"><p>The uthash macros fall into two categories. The <em>convenience</em> macros can be used
with integer, pointer or string keys (and require that you chose the conventional
name <tt>hh</tt> for the <tt>UT_hash_handle</tt> field).  The convenience macros take fewer
arguments than the general macros, making their usage a bit simpler for these
common types of keys.</p></div>
<div class="paragraph"><p>The <em>general</em> macros can be used for any types of keys, or for multi-field keys,
or when the <tt>UT_hash_handle</tt> has been named something other than <tt>hh</tt>. These
macros take more arguments and offer greater flexibility in return. But if the
convenience macros suit your needs, use them-- your code will be more readable.</p></div>
</div></div>
<div class="sect2">
<h3 id="_declare_the_hash">Declare the hash</h3>
<div class="paragraph"><p>Your hash must be declared as a <tt>NULL</tt>-initialized pointer to your structure.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>struct my_struct *users = NULL;    /* important! initialize to NULL */</tt></pre>
</div></div>
</div>
<div class="sect2">
<h3 id="_add_item">Add item</h3>
<div class="paragraph"><p>Allocate and initialize your structure as you see fit. The only aspect
of this that matters to uthash is that your key must be initialized to
a unique value. Then call <tt>HASH_ADD</tt>. (Here we use the convenience macro
<tt>HASH_ADD_INT</tt>, which offers simplified usage for keys of type <tt>int</tt>).</p></div>
<div class="listingblock">
<div class="title">Add an item to a hash</div>
<div class="content">
<pre><tt>void add_user(int user_id, char *name) {
    struct my_struct *s;

    s = malloc(sizeof(struct my_struct));
    s-&gt;id = user_id;
    strcpy(s-&gt;name, name);
    HASH_ADD_INT( users, id, s );  /* id: name of key field */
}</tt></pre>
</div></div>
<div class="paragraph"><p>The first parameter to <tt>HASH_ADD_INT</tt> is the hash table, and the
second parameter is the <em>name</em> of the key field. Here, this is <tt>id</tt>. The
last parameter is a pointer to the structure being added.</p></div>
<div class="sidebarblock" id="validc">
<div class="content">
<div class="title">Wait.. the field name is a parameter?</div>
<div class="paragraph"><p>If you find it strange that <tt>id</tt>, which is the <em>name of a field</em> in the
structure, can be passed as a parameter, welcome to the world of macros. Don&#8217;t
worry- the C preprocessor expands this to valid C code.</p></div>
</div></div>
<div class="sect3">
<h4 id="_key_must_not_be_modified_while_in_use">Key must not be modified while in-use</h4>
<div class="paragraph"><p>Once a structure has been added to the hash, do not change the value of its key.
Instead, delete the item from the hash, change the key, and then re-add it.</p></div>
</div>
<div class="sect3">
<h4 id="_checking_uniquness">Checking uniquness</h4>
<div class="paragraph"><p>In the example above, we didn&#8217;t check to see if <tt>user_id</tt> was already a key
of some existing item in the hash. <strong>If there&#8217;s any chance that duplicate keys
could be generated by your program, you must explicitly check the uniqueness</strong>
before adding the key to the hash. If the key is already in the hash, you can
simply modify the existing structure in the hash rather than adding the item.
<em>It is an error to add two items with the same key to the hash table</em>.</p></div>
<div class="paragraph"><p>Let&#8217;s rewrite the <tt>add_user</tt> function to check whether the id is in the hash.
Only if the id is not present in the hash, do we create the item and add it.
Otherwise we just modify the structure that already exists.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>void add_user(int user_id, char *name) {
    struct my_struct *s;</tt></pre>
</div></div>
<div class="literalblock">
<div class="content">
<pre><tt>    HASH_FIND_INT(users, &amp;user_id, s);  /* id already in the hash? */
    if (s==NULL) {
      s = (struct my_struct*)malloc(sizeof(struct my_struct));
      s-&gt;id = user_id;
      HASH_ADD_INT( users, id, s );  /* id: name of key field */
    }
    strcpy(s-&gt;name, name);
}</tt></pre>
</div></div>
<div class="paragraph"><p>Why doesn&#8217;t uthash check key uniqueness for you? It saves the cost of a hash
lookup for those programs which don&#8217;t need it- for example, programs whose keys
are generated by an incrementing, non-repeating counter.</p></div>
<div class="paragraph"><p>However, if replacement is a common operation, it is possible to use the
<tt>HASH_REPLACE</tt> macro. This macro, before adding the item, will try to find an
item with the same key and delete it first. It also returns a pointer to the
replaced item, so the user has a chance to de-allocate its memory.</p></div>
</div>
<div class="sect3">
<h4 id="_passing_the_hash_pointer_into_functions">Passing the hash pointer into functions</h4>
<div class="paragraph"><p>In the example above <tt>users</tt> is a global variable, but what if the caller wanted
to pass the hash pointer <em>into</em> the <tt>add_user</tt> function? At first glance it would
appear that you could simply pass <tt>users</tt> as an argument, but that won&#8217;t work
right.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>/* bad */
void add_user(struct my_struct *users, int user_id, char *name) {
  ...
  HASH_ADD_INT( users, id, s );
}</tt></pre>
</div></div>
<div class="paragraph"><p>You really need to pass <em>a pointer</em> to the hash pointer:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>/* good */
void add_user(struct my_struct **users, int user_id, char *name) { ...
  ...
  HASH_ADD_INT( *users, id, s );
}</tt></pre>
</div></div>
<div class="paragraph"><p>Note that we dereferenced the pointer in the <tt>HASH_ADD</tt> also.</p></div>
<div class="paragraph"><p>The reason it&#8217;s necessary to deal with a pointer to the hash pointer is simple:
the hash macros modify it (in other words, they modify the <em>pointer itself</em> not
just what it points to).</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_replace_item">Replace item</h3>
<div class="paragraph"><p><tt>HASH_REPLACE</tt> macros are equivalent to HASH_ADD macros except they attempt
to find and delete the item first. If it find and deletes and item, it will
also return that items pointer as an output parameter.</p></div>
</div>
<div class="sect2">
<h3 id="_find_item">Find item</h3>
<div class="paragraph"><p>To look up a structure in a hash, you need its key.  Then call <tt>HASH_FIND</tt>.
(Here we use the convenience macro <tt>HASH_FIND_INT</tt> for keys of type <tt>int</tt>).</p></div>
<div class="listingblock">
<div class="title">Find a structure using its key</div>
<div class="content">
<pre><tt>struct my_struct *find_user(int user_id) {
    struct my_struct *s;

    HASH_FIND_INT( users, &amp;user_id, s );  /* s: output pointer */
    return s;
}</tt></pre>
</div></div>
<div class="paragraph"><p>Here, the hash table is <tt>users</tt>, and <tt>&amp;user_id</tt> points to the key (an integer
in this case).  Last, <tt>s</tt> is the <em>output</em> variable of <tt>HASH_FIND_INT</tt>. The
final result is that <tt>s</tt> points to the structure with the given key, or
is <tt>NULL</tt> if the key wasn&#8217;t found in the hash.</p></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">The middle argument is a <em>pointer</em> to the key. You can&#8217;t pass a literal key
value to <tt>HASH_FIND</tt>. Instead assign the literal value to a variable, and pass
a pointer to the variable.</td>
</tr></table>
</div>
</div>
<div class="sect2">
<h3 id="_delete_item">Delete item</h3>
<div class="paragraph"><p>To delete a structure from a hash, you must have a pointer to it. (If you only
have the key, first do a <tt>HASH_FIND</tt> to get the structure pointer).</p></div>
<div class="listingblock">
<div class="title">Delete an item from a hash</div>
<div class="content">
<pre><tt>void delete_user(struct my_struct *user) {
    HASH_DEL( users, user);  /* user: pointer to deletee */
    free(user);              /* optional; it's up to you! */
}</tt></pre>
</div></div>
<div class="paragraph"><p>Here again, <tt>users</tt> is the hash table, and <tt>user</tt> is a pointer to the
structure we want to remove from the hash.</p></div>
<div class="sect3">
<h4 id="_uthash_never_frees_your_structure">uthash never frees your structure</h4>
<div class="paragraph"><p>Deleting a structure just removes it from the hash table-- it doesn&#8217;t <tt>free</tt>
it.  The choice of when to free your structure is entirely up to you; uthash
will never free your structure. For example when using <tt>HASH_REPLACE</tt> macros,
a replaced output argument is returned back, in order to make it possible for
the user to de-allocate it.</p></div>
</div>
<div class="sect3">
<h4 id="_delete_can_change_the_pointer">Delete can change the pointer</h4>
<div class="paragraph"><p>The hash table pointer (which initially points to the first item added to the
hash) can change in response to <tt>HASH_DEL</tt> (i.e. if you delete the first item
in the hash table).</p></div>
</div>
<div class="sect3">
<h4 id="_iterative_deletion">Iterative deletion</h4>
<div class="paragraph"><p>The <tt>HASH_ITER</tt> macro is a deletion-safe iteration construct which expands
to a simple <em>for</em> loop.</p></div>
<div class="listingblock">
<div class="title">Delete all items from a hash</div>
<div class="content">
<pre><tt>void delete_all() {
  struct my_struct *current_user, *tmp;

  HASH_ITER(hh, users, current_user, tmp) {
    HASH_DEL(users,current_user);  /* delete; users advances to next */
    free(current_user);            /* optional- if you want to free  */
  }
}</tt></pre>
</div></div>
</div>
<div class="sect3">
<h4 id="_all_at_once_deletion">All-at-once deletion</h4>
<div class="paragraph"><p>If you only want to delete all the items, but not free them or do any
per-element clean up, you can do this more efficiently in a single operation:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>HASH_CLEAR(hh,users);</tt></pre>
</div></div>
<div class="paragraph"><p>Afterward, the list head (here, <tt>users</tt>) will be set to <tt>NULL</tt>.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_count_items">Count items</h3>
<div class="paragraph"><p>The number of items in the hash table can be obtained using <tt>HASH_COUNT</tt>:</p></div>
<div class="listingblock">
<div class="title">Count of items in the hash table</div>
<div class="content">
<pre><tt>unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);</tt></pre>
</div></div>
<div class="paragraph"><p>Incidentally, this works even the list (<tt>users</tt>, here) is <tt>NULL</tt>, in
which case the count is 0.</p></div>
</div>
<div class="sect2">
<h3 id="_iterating_and_sorting">Iterating and sorting</h3>
<div class="paragraph"><p>You can loop over the items in the hash by starting from the beginning and
following the <tt>hh.next</tt> pointer.</p></div>
<div class="listingblock">
<div class="title">Iterating over all the items in a hash</div>
<div class="content">
<pre><tt>void print_users() {
    struct my_struct *s;

    for(s=users; s != NULL; s=s-&gt;hh.next) {
        printf("user id %d: name %s\n", s-&gt;id, s-&gt;name);
    }
}</tt></pre>
</div></div>
<div class="paragraph"><p>There is also an <tt>hh.prev</tt> pointer you could use to iterate backwards through
the hash, starting from any known item.</p></div>
<div class="sect3">
<h4 id="deletesafe">Deletion-safe iteration</h4>
<div class="paragraph"><p>In the example above, it would not be safe to delete and free <tt>s</tt> in the body
of the <em>for</em> loop, (because <tt>s</tt> is derefenced each time the loop iterates).
This is easy to rewrite correctly (by copying the <tt>s-&gt;hh.next</tt> pointer to a
temporary variable <em>before</em> freeing <tt>s</tt>), but it comes up often enough that a
deletion-safe iteration macro, <tt>HASH_ITER</tt>, is included. It expands to a
<tt>for</tt>-loop header. Here is how it could be used to rewrite the last example:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>struct my_struct *s, *tmp;</tt></pre>
</div></div>
<div class="literalblock">
<div class="content">
<pre><tt>HASH_ITER(hh, users, s, tmp) {
    printf("user id %d: name %s\n", s-&gt;id, s-&gt;name);
    /* ... it is safe to delete and free s here */
}</tt></pre>
</div></div>
<div class="sidebarblock">
<div class="content">
<div class="title">A hash is also a doubly-linked list.</div>
<div class="paragraph"><p>Iterating backward and forward through the items in the hash is possible
because of the <tt>hh.prev</tt> and <tt>hh.next</tt> fields. All the items in the hash can
be reached by repeatedly following these pointers, thus the hash is also a
doubly-linked list.</p></div>
</div></div>
<div class="paragraph"><p>If you&#8217;re using uthash in a C++ program, you need an extra cast on the <tt>for</tt>
iterator, e.g., <tt>s=(struct my_struct*)s-&gt;hh.next</tt>.</p></div>
</div>
<div class="sect3">
<h4 id="_sorting">Sorting</h4>
<div class="paragraph"><p>The items in the hash are visited in "insertion order" when you follow the
<tt>hh.next</tt> pointer. You can sort the items into a new order using <tt>HASH_SORT</tt>.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>HASH_SORT( users, name_sort );</tt></pre>
</div></div>
<div class="paragraph"><p>The second argument is a pointer to a comparison function. It must accept two
pointer arguments (the items to compare), and must return an <tt>int</tt> which is
less than zero, zero, or greater than zero, if the first item sorts before,
equal to, or after the second item, respectively. (This is the same convention
used by <tt>strcmp</tt> or <tt>qsort</tt> in the standard C library).</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>int sort_function(void *a, void *b) {
  /* compare a to b (cast a and b appropriately)
   * return (int) -1 if (a &lt; b)
   * return (int)  0 if (a == b)
   * return (int)  1 if (a &gt; b)
   */
}</tt></pre>
</div></div>
<div class="paragraph"><p>Below, <tt>name_sort</tt> and <tt>id_sort</tt> are two examples of sort functions.</p></div>
<div class="listingblock">
<div class="title">Sorting the items in the hash</div>
<div class="content">
<pre><tt>int name_sort(struct my_struct *a, struct my_struct *b) {
    return strcmp(a-&gt;name,b-&gt;name);
}

int id_sort(struct my_struct *a, struct my_struct *b) {
    return (a-&gt;id - b-&gt;id);
}

void sort_by_name() {
    HASH_SORT(users, name_sort);
}

void sort_by_id() {
    HASH_SORT(users, id_sort);
}</tt></pre>
</div></div>
<div class="paragraph"><p>When the items in the hash are sorted, the first item may change position.  In
the example above, <tt>users</tt> may point to a different structure after calling
<tt>HASH_SORT</tt>.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_a_complete_example">A complete example</h3>
<div class="paragraph"><p>We&#8217;ll repeat all the code and embellish it with a <tt>main()</tt> function to form a
working example.</p></div>
<div class="paragraph"><p>If this code was placed in a file called <tt>example.c</tt> in the same directory as
<tt>uthash.h</tt>, it could be compiled and run like this:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>cc -o example example.c
./example</tt></pre>
</div></div>
<div class="paragraph"><p>Follow the prompts to try the program.</p></div>
<div class="listingblock">
<div class="title">A complete program</div>
<div class="content">
<pre><tt>#include &lt;stdio.h&gt;   /* gets */
#include &lt;stdlib.h&gt;  /* atoi, malloc */
#include &lt;string.h&gt;  /* strcpy */
#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};

struct my_struct *users = NULL;

void add_user(int user_id, char *name) {
    struct my_struct *s;

    HASH_FIND_INT(users, &amp;user_id, s);  /* id already in the hash? */
    if (s==NULL) {
      s = (struct my_struct*)malloc(sizeof(struct my_struct));
      s-&gt;id = user_id;
      HASH_ADD_INT( users, id, s );  /* id: name of key field */
    }
    strcpy(s-&gt;name, name);
}

struct my_struct *find_user(int user_id) {
    struct my_struct *s;

    HASH_FIND_INT( users, &amp;user_id, s );  /* s: output pointer */
    return s;
}

void delete_user(struct my_struct *user) {
    HASH_DEL( users, user);  /* user: pointer to deletee */
    free(user);
}

void delete_all() {
  struct my_struct *current_user, *tmp;

  HASH_ITER(hh, users, current_user, tmp) {
    HASH_DEL(users,current_user);  /* delete it (users advances to next) */
    free(current_user);            /* free it */
  }
}

void print_users() {
    struct my_struct *s;

    for(s=users; s != NULL; s=(struct my_struct*)(s-&gt;hh.next)) {
        printf("user id %d: name %s\n", s-&gt;id, s-&gt;name);
    }
}

int name_sort(struct my_struct *a, struct my_struct *b) {
    return strcmp(a-&gt;name,b-&gt;name);
}

int id_sort(struct my_struct *a, struct my_struct *b) {
    return (a-&gt;id - b-&gt;id);
}

void sort_by_name() {
    HASH_SORT(users, name_sort);
}

void sort_by_id() {
    HASH_SORT(users, id_sort);
}

int main(int argc, char *argv[]) {
    char in[10];
    int id=1, running=1;
    struct my_struct *s;
    unsigned num_users;

    while (running) {
        printf(" 1. add user\n");
        printf(" 2. add/rename user by id\n");
        printf(" 3. find user\n");
        printf(" 4. delete user\n");
        printf(" 5. delete all users\n");
        printf(" 6. sort items by name\n");
        printf(" 7. sort items by id\n");
        printf(" 8. print users\n");
        printf(" 9. count users\n");
        printf("10. quit\n");
        gets(in);
        switch(atoi(in)) {
            case 1:
                printf("name?\n");
                add_user(id++, gets(in));
                break;
            case 2:
                printf("id?\n");
                gets(in); id = atoi(in);
                printf("name?\n");
                add_user(id, gets(in));
                break;
            case 3:
                printf("id?\n");
                s = find_user(atoi(gets(in)));
                printf("user: %s\n", s ? s-&gt;name : "unknown");
                break;
            case 4:
                printf("id?\n");
                s = find_user(atoi(gets(in)));
                if (s) delete_user(s);
                else printf("id unknown\n");
                break;
            case 5:
                delete_all();
                break;
            case 6:
                sort_by_name();
                break;
            case 7:
                sort_by_id();
                break;
            case 8:
                print_users();
                break;
            case 9:
                num_users=HASH_COUNT(users);
                printf("there are %u users\n", num_users);
                break;
            case 10:
                running=0;
                break;
        }
    }

    delete_all();  /* free any structures */
    return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This program is included in the distribution in <tt>tests/example.c</tt>. You can run
<tt>make example</tt> in that directory to compile it easily.</p></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_standard_key_types">Standard key types</h2>
<div class="sectionbody">
<div class="paragraph"><p>This section goes into specifics of how to work with different kinds of keys.
You can use nearly any type of key-- integers, strings, pointers, structures, etc.</p></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="title">A note about float</div>
<div class="paragraph"><p>You can use floating point keys. This comes with the same caveats as with any
program that tests floating point equality. In other words, even the tiniest
difference in two floating point numbers makes them distinct keys.</p></div>
</td>
</tr></table>
</div>
<div class="sect2">
<h3 id="_integer_keys">Integer keys</h3>
<div class="paragraph"><p>The preceding examples demonstrated use of integer keys. To recap, use the
convenience macros <tt>HASH_ADD_INT</tt> and <tt>HASH_FIND_INT</tt> for structures with
integer keys. (The other operations such as <tt>HASH_DELETE</tt> and <tt>HASH_SORT</tt> are
the same for all types of keys).</p></div>
</div>
<div class="sect2">
<h3 id="_string_keys">String keys</h3>
<div class="paragraph"><p>If your structure has a string key, the operations to use depend on whether your
structure <em>points to</em> the key (<tt>char *</tt>) or the string resides <tt>within</tt> the
structure (<tt>char a[10]</tt>).  <strong>This distinction is important</strong>.  As we&#8217;ll see below,
you need to use <tt>HASH_ADD_KEYPTR</tt> when your structure <em>points</em> to a key (that is,
the key itself is <em>outside</em> of the structure); in contrast, use <tt>HASH_ADD_STR</tt>
for a string key that is contained <strong>within</strong> your structure.</p></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="title">char[ ] vs. char*</div>
<div class="paragraph"><p>The string is <em>within</em> the structure in the first example below-- <tt>name</tt> is a
<tt>char[10]</tt> field.  In the second example, the key is <em>outside</em> of the
structure-- <tt>name</tt> is a <tt>char *</tt>. So the first example uses <tt>HASH_ADD_STR</tt> but
the second example uses <tt>HASH_ADD_KEYPTR</tt>.  For information on this macro, see
the <a href="#Macro_reference">Macro reference</a>.</p></div>
</td>
</tr></table>
</div>
<div class="sect3">
<h4 id="_string_em_within_em_structure">String <em>within</em> structure</h4>
<div class="listingblock">
<div class="title">A string-keyed hash (string within structure)</div>
<div class="content">
<pre><tt>#include &lt;string.h&gt;  /* strcpy */
#include &lt;stdlib.h&gt;  /* malloc */
#include &lt;stdio.h&gt;   /* printf */
#include "uthash.h"

struct my_struct {
    char name[10];             /* key (string is WITHIN the structure) */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int main(int argc, char *argv[]) {
    const char **n, *names[] = { "joe", "bob", "betty", NULL };
    struct my_struct *s, *tmp, *users = NULL;
    int i=0;

    for (n = names; *n != NULL; n++) {
        s = (struct my_struct*)malloc(sizeof(struct my_struct));
        strncpy(s-&gt;name, *n,10);
        s-&gt;id = i++;
        HASH_ADD_STR( users, name, s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d\n", s-&gt;id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This example is included in the distribution in <tt>tests/test15.c</tt>. It prints:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>betty's id is 2</tt></pre>
</div></div>
</div>
<div class="sect3">
<h4 id="_string_em_pointer_em_in_structure">String <em>pointer</em> in structure</h4>
<div class="paragraph"><p>Now, here is the same example but using a <tt>char *</tt> key instead of <tt>char [ ]</tt>:</p></div>
<div class="listingblock">
<div class="title">A string-keyed hash (structure points to string)</div>
<div class="content">
<pre><tt>#include &lt;string.h&gt;  /* strcpy */
#include &lt;stdlib.h&gt;  /* malloc */
#include &lt;stdio.h&gt;   /* printf */
#include "uthash.h"

struct my_struct {
    const char *name;          /* key */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int main(int argc, char *argv[]) {
    const char **n, *names[] = { "joe", "bob", "betty", NULL };
    struct my_struct *s, *tmp, *users = NULL;
    int i=0;

    for (n = names; *n != NULL; n++) {
        s = (struct my_struct*)malloc(sizeof(struct my_struct));
        s-&gt;name = *n;
        s-&gt;id = i++;
        HASH_ADD_KEYPTR( hh, users, s-&gt;name, strlen(s-&gt;name), s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d\n", s-&gt;id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This example is included in <tt>tests/test40.c</tt>.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_pointer_keys">Pointer keys</h3>
<div class="paragraph"><p>Your key can be a pointer. To be very clear, this means the <em>pointer itself</em>
can be the key (in contrast, if the thing <em>pointed to</em> is the key, this is a
different use case handled by <tt>HASH_ADD_KEYPTR</tt>).</p></div>
<div class="paragraph"><p>Here is a simple example where a structure has a pointer member, called <tt>key</tt>.</p></div>
<div class="listingblock">
<div class="title">A pointer key</div>
<div class="content">
<pre><tt>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include "uthash.h"

typedef struct {
  void *key;
  int i;
  UT_hash_handle hh;
} el_t;

el_t *hash = NULL;
char *someaddr = NULL;

int main() {
  el_t *d;
  el_t *e = (el_t*)malloc(sizeof(el_t));
  if (!e) return -1;
  e-&gt;key = (void*)someaddr;
  e-&gt;i = 1;
  HASH_ADD_PTR(hash,key,e);
  HASH_FIND_PTR(hash, &amp;someaddr, d);
  if (d) printf("found\n");

  /* release memory */
  HASH_DEL(hash,e);
  free(e);
  return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This example is included in <tt>tests/test57.c</tt>. Note that the end of the program
deletes the element out of the hash, (and since no more elements remain in the
hash), uthash releases its internal memory.</p></div>
</div>
<div class="sect2">
<h3 id="_structure_keys">Structure keys</h3>
<div class="paragraph"><p>Your key field can have any data type. To uthash, it is just a sequence of
bytes.  Therefore, even a nested structure can be used as a key. We&#8217;ll use the
general macros <tt>HASH_ADD</tt> and <tt>HASH_FIND</tt> to demonstrate.</p></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">Structures contain padding (wasted internal space used to fulfill
alignment requirements for the members of the structure). These padding bytes
<em>must be zeroed</em> before adding an item to the hash or looking up an item.
Therefore always zero the whole structure before setting the members of
interest. The example below does this-- see the two calls to <tt>memset</tt>.</td>
</tr></table>
</div>
<div class="listingblock">
<div class="title">A key which is a structure</div>
<div class="content">
<pre><tt>#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include "uthash.h"

typedef struct {
  char a;
  int b;
} record_key_t;

typedef struct {
    record_key_t key;
    /* ... other data ... */
    UT_hash_handle hh;
} record_t;

int main(int argc, char *argv[]) {
    record_t l, *p, *r, *tmp, *records = NULL;

    r = (record_t*)malloc( sizeof(record_t) );
    memset(r, 0, sizeof(record_t));
    r-&gt;key.a = 'a';
    r-&gt;key.b = 1;
    HASH_ADD(hh, records, key, sizeof(record_key_t), r);

    memset(&amp;l, 0, sizeof(record_t));
    l.key.a = 'a';
    l.key.b = 1;
    HASH_FIND(hh, records, &amp;l.key, sizeof(record_key_t), p);

    if (p) printf("found %c %d\n", p-&gt;key.a, p-&gt;key.b);

    HASH_ITER(hh, records, p, tmp) {
      HASH_DEL(records, p);
      free(p);
    }
    return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This usage is nearly the same as use of a compound key explained below.</p></div>
<div class="paragraph"><p>Note that the general macros require the name of the <tt>UT_hash_handle</tt> to be
passed as the first argument (here, this is <tt>hh</tt>). The general macros are
documented in <a href="#Macro_reference">Macro Reference</a>.</p></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_advanced_topics">Advanced Topics</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_compound_keys">Compound keys</h3>
<div class="paragraph"><p>Your key can even comprise multiple contiguous fields.</p></div>
<div class="listingblock">
<div class="title">A multi-field key</div>
<div class="content">
<pre><tt>#include &lt;stdlib.h&gt;    /* malloc       */
#include &lt;stddef.h&gt;    /* offsetof     */
#include &lt;stdio.h&gt;     /* printf       */
#include &lt;string.h&gt;    /* memset       */
#include "uthash.h"

#define UTF32 1

typedef struct {
  UT_hash_handle hh;
  int len;
  char encoding;      /* these two fields */
  int text[];         /* comprise the key */
} msg_t;

typedef struct {
    char encoding;
    int text[];
} lookup_key_t;

int main(int argc, char *argv[]) {
    unsigned keylen;
    msg_t *msg, *tmp, *msgs = NULL;
    lookup_key_t *lookup_key;

    int beijing[] = {0x5317, 0x4eac};   /* UTF-32LE for 北京 */

    /* allocate and initialize our structure */
    msg = (msg_t*)malloc( sizeof(msg_t) + sizeof(beijing) );
    memset(msg, 0, sizeof(msg_t)+sizeof(beijing)); /* zero fill */
    msg-&gt;len = sizeof(beijing);
    msg-&gt;encoding = UTF32;
    memcpy(msg-&gt;text, beijing, sizeof(beijing));

    /* calculate the key length including padding, using formula */
    keylen =   offsetof(msg_t, text)       /* offset of last key field */
             + sizeof(beijing)             /* size of last key field */
             - offsetof(msg_t, encoding);  /* offset of first key field */

    /* add our structure to the hash table */
    HASH_ADD( hh, msgs, encoding, keylen, msg);

    /* look it up to prove that it worked :-) */
    msg=NULL;

    lookup_key = (lookup_key_t*)malloc(sizeof(*lookup_key) + sizeof(beijing));
    memset(lookup_key, 0, sizeof(*lookup_key) + sizeof(beijing));
    lookup_key-&gt;encoding = UTF32;
    memcpy(lookup_key-&gt;text, beijing, sizeof(beijing));
    HASH_FIND( hh, msgs, &amp;lookup_key-&gt;encoding, keylen, msg );
    if (msg) printf("found \n");
    free(lookup_key);

    HASH_ITER(hh, msgs, msg, tmp) {
      HASH_DEL(msgs, msg);
      free(msg);
    }
    return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>This example is included in the distribution in <tt>tests/test22.c</tt>.</p></div>
<div class="paragraph"><p>If you use multi-field keys, recognize that the compiler pads adjacent fields
(by inserting unused space between them) in order to fulfill the alignment
requirement of each field. For example a structure containing a <tt>char</tt> followed
by an <tt>int</tt> will normally have 3 "wasted" bytes of padding after the char, in
order to make the <tt>int</tt> field start on a multiple-of-4 address (4 is the length
of the int).</p></div>
<div class="sidebarblock">
<div class="content">
<div class="title">Calculating the length of a multi-field key:</div>
<div class="paragraph"><p>To determine the key length when using a multi-field key, you must include any
intervening structure padding the compiler adds for alignment purposes.</p></div>
<div class="paragraph"><p>An easy way to calculate the key length is to use the <tt>offsetof</tt> macro from
<tt>&lt;stddef.h&gt;</tt>.  The formula is:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>key length =   offsetof(last_key_field)
             + sizeof(last_key_field)
             - offsetof(first_key_field)</tt></pre>
</div></div>
<div class="paragraph"><p>In the example above, the <tt>keylen</tt> variable is set using this formula.</p></div>
</div></div>
<div class="paragraph"><p>When dealing with a multi-field key, you must zero-fill your structure before
<tt>HASH_ADD</tt>'ing it to a hash table, or using its fields in a <tt>HASH_FIND</tt> key.</p></div>
<div class="paragraph"><p>In the previous example, <tt>memset</tt> is used to initialize the structure by
zero-filling it. This zeroes out any padding between the key fields. If we
didn&#8217;t zero-fill the structure, this padding would contain random values.  The
random values would lead to <tt>HASH_FIND</tt> failures; as two "identical" keys will
appear to mismatch if there are any differences within their padding.</p></div>
</div>
<div class="sect2">
<h3 id="multilevel">Multi-level hash tables</h3>
<div class="paragraph"><p>A multi-level hash table arises when each element of a hash table contains its
own secondary hash table. There can be any number of levels. In a scripting
language you might see:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>$items{bob}{age}=37</tt></pre>
</div></div>
<div class="paragraph"><p>The C program below builds this example in uthash: the hash table is called
<tt>items</tt>. It contains one element (<tt>bob</tt>) whose own hash table contains one
element (<tt>age</tt>) with value 37.  No special functions are necessary to build
a multi-level hash table.</p></div>
<div class="paragraph"><p>While this example represents both levels (<tt>bob</tt> and <tt>age</tt>) using the same
structure, it would also be fine to use two different structure definitions.
It would also be fine if there were three or more levels instead of two.</p></div>
<div class="listingblock">
<div class="title">Multi-level hash table</div>
<div class="content">
<pre><tt>#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
#include "uthash.h"

/* hash of hashes */
typedef struct item {
  char name[10];
  struct item *sub;
  int val;
  UT_hash_handle hh;
} item_t;

item_t *items=NULL;

int main(int argc, char *argvp[]) {
  item_t *item1, *item2, *tmp1, *tmp2;

  /* make initial element */
  item_t *i = malloc(sizeof(*i));
  strcpy(i-&gt;name, "bob");
  i-&gt;sub = NULL;
  i-&gt;val = 0;
  HASH_ADD_STR(items, name, i);

  /* add a sub hash table off this element */
  item_t *s = malloc(sizeof(*s));
  strcpy(s-&gt;name, "age");
  s-&gt;sub = NULL;
  s-&gt;val = 37;
  HASH_ADD_STR(i-&gt;sub, name, s);

  /* iterate over hash elements  */
  HASH_ITER(hh, items, item1, tmp1) {
    HASH_ITER(hh, item1-&gt;sub, item2, tmp2) {
      printf("$items{%s}{%s} = %d\n", item1-&gt;name, item2-&gt;name, item2-&gt;val);
    }
  }

  /* clean up both hash tables */
  HASH_ITER(hh, items, item1, tmp1) {
    HASH_ITER(hh, item1-&gt;sub, item2, tmp2) {
      HASH_DEL(item1-&gt;sub, item2);
      free(item2);
    }
    HASH_DEL(items, item1);
    free(item1);
  }

  return 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>The example above is included in <tt>tests/test59.c</tt>.</p></div>
</div>
<div class="sect2">
<h3 id="multihash">Items in several hash tables</h3>
<div class="paragraph"><p>A structure can be added to more than one hash table. A few reasons you might do
this include:</p></div>
<div class="ulist"><ul>
<li>
<p>
each hash table may use an alternative key;
</p>
</li>
<li>
<p>
each hash table may have its own sort order;
</p>
</li>
<li>
<p>
or you might simply use multiple hash tables for grouping purposes.  E.g.,
  you could have users in an <tt>admin_users</tt> and a <tt>users</tt> hash table.
</p>
</li>
</ul></div>
<div class="paragraph"><p>Your structure needs to have a <tt>UT_hash_handle</tt> field for each hash table to
which it might be added. You can name them anything. E.g.,</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>UT_hash_handle hh1, hh2;</tt></pre>
</div></div>
</div>
<div class="sect2">
<h3 id="_items_with_alternative_keys">Items with alternative keys</h3>
<div class="paragraph"><p>You might create a hash table keyed on an ID field, and another hash table keyed
on username (if usernames are unique). You can add the same user structure to
both hash tables (without duplication of the structure), allowing lookup of a
user structure by their name or ID.  The way to achieve this is to have a
separate <tt>UT_hash_handle</tt> for each hash to which the structure may be added.</p></div>
<div class="listingblock">
<div class="title">A structure with two alternative keys</div>
<div class="content">
<pre><tt>struct my_struct {
    int id;                    /* usual key */
    char username[10];         /* alternative key */
    UT_hash_handle hh1;        /* handle for first hash table */
    UT_hash_handle hh2;        /* handle for second hash table */
};</tt></pre>
</div></div>
<div class="paragraph"><p>In the example above, the structure can now be added to two separate hash
tables. In one hash, <tt>id</tt> is its key, while in the other hash, <tt>username</tt> is
its key.  (There is no requirement that the two hashes have different key
fields. They could both use the same key, such as <tt>id</tt>).</p></div>
<div class="paragraph"><p>Notice the structure has two hash handles (<tt>hh1</tt> and <tt>hh2</tt>).  In the code
below, notice that each hash handle is used exclusively with a particular hash
table.  (<tt>hh1</tt> is always used with the <tt>users_by_id</tt> hash, while <tt>hh2</tt> is
always used with the <tt>users_by_name</tt> hash table).</p></div>
<div class="listingblock">
<div class="title">Two keys on a structure</div>
<div class="content">
<pre><tt>    struct my_struct *users_by_id = NULL, *users_by_name = NULL, *s;
    int i;
    char *name;

    s = malloc(sizeof(struct my_struct));
    s-&gt;id = 1;
    strcpy(s-&gt;username, "thanson");

    /* add the structure to both hash tables */
    HASH_ADD(hh1, users_by_id, id, sizeof(int), s);
    HASH_ADD(hh2, users_by_name, username, strlen(s-&gt;username), s);

    /* lookup user by ID in the "users_by_id" hash table */
    i=1;
    HASH_FIND(hh1, users_by_id, &amp;i, sizeof(int), s);
    if (s) printf("found id %d: %s\n", i, s-&gt;username);

    /* lookup user by username in the "users_by_name" hash table */
    name = "thanson";
    HASH_FIND(hh2, users_by_name, name, strlen(name), s);
    if (s) printf("found user %s: %d\n", name, s-&gt;id);</tt></pre>
</div></div>
</div>
<div class="sect2">
<h3 id="_several_sort_orders">Several sort orders</h3>
<div class="paragraph"><p>It comes as no suprise that two hash tables can have different sort orders, but
this fact can also be used advantageously to sort the <em>same items</em> in several
ways. This is based on the ability to store a structure in several hash tables.</p></div>
<div class="paragraph"><p>Extending the previous example, suppose we have many users. We have added each
user structure to the <tt>users_by_id</tt> hash table and the <tt>users_by_name</tt> hash table.
(To reiterate, this is done without the need to have two copies of each structure).
Now we can define two sort functions, then use <tt>HASH_SRT</tt>.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>int sort_by_id(struct my_struct *a, struct my_struct *b) {
  if (a-&gt;id == b-&gt;id) return 0;
  return (a-&gt;id &lt; b-&gt;id) ? -1 : 1;
}</tt></pre>
</div></div>
<div class="literalblock">
<div class="content">
<pre><tt>int sort_by_name(struct my_struct *a, struct my_struct *b) {
  return strcmp(a-&gt;username,b-&gt;username);
}</tt></pre>
</div></div>
<div class="literalblock">
<div class="content">
<pre><tt>HASH_SRT(hh1, users_by_id, sort_by_id);
HASH_SRT(hh2, users_by_name, sort_by_name);</tt></pre>
</div></div>
<div class="paragraph"><p>Now iterating over the items in <tt>users_by_id</tt> will traverse them in id-order
while, naturally, iterating over <tt>users_by_name</tt> will traverse them in
name-order. The items are fully forward-and-backward linked in each order.
So even for one set of users, we might store them in two hash tables to provide
easy iteration in two different sort orders.</p></div>
</div>
<div class="sect2">
<h3 id="_bloom_filter_faster_misses">Bloom filter (faster misses)</h3>
<div class="paragraph"><p>Programs that generate a fair miss rate (<tt>HASH_FIND</tt> that result in <tt>NULL</tt>) may
benefit from the built-in Bloom filter support. This is disabled by default,
because programs that generate only hits would incur a slight penalty from it.
Also, programs that do deletes should not use the Bloom filter. While the
program would operate correctly, deletes diminish the benefit of the filter.
To enable the Bloom filter, simply compile with <tt>-DHASH_BLOOM=n</tt> like:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>-DHASH_BLOOM=27</tt></pre>
</div></div>
<div class="paragraph"><p>where the number can be any value up to 32 which determines the amount of memory
used by the filter, as shown below. Using more memory makes the filter more
accurate and has the potential to speed up your program by making misses bail
out faster.</p></div>
<div class="tableblock">
<table rules="none"
width="50%"
frame="border"
cellspacing="0" cellpadding="4">
<caption class="title">Table 1. Bloom filter sizes for selected values of n</caption>
<col width="25%" />
<col width="75%" />
<thead>
<tr>
<th align="left" valign="top"> n   </th>
<th align="left" valign="top"> Bloom filter size (per hash table)</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left" valign="top"><p class="table"><tt>16</tt></p></td>
<td align="left" valign="top"><p class="table">8 kilobytes</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>20</tt></p></td>
<td align="left" valign="top"><p class="table">128 kilobytes</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>24</tt></p></td>
<td align="left" valign="top"><p class="table">2 megabytes</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>28</tt></p></td>
<td align="left" valign="top"><p class="table">32 megabytes</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>32</tt></p></td>
<td align="left" valign="top"><p class="table">512 megabytes</p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p>Bloom filters are only a performance feature; they do not change the results of
hash operations in any way. The only way to gauge whether or not a Bloom filter
is right for your program is to test it. Reasonable values for the size of the
Bloom filter are 16-32 bits.</p></div>
</div>
<div class="sect2">
<h3 id="_select">Select</h3>
<div class="paragraph"><p>An experimental <em>select</em> operation is provided that inserts those items from a
source hash that satisfy a given condition into a destination hash. This
insertion is done with somewhat more efficiency than if this were using
<tt>HASH_ADD</tt>, namely because the hash function is not recalculated for keys of the
selected items.  This operation does not remove any items from the source hash.
Rather the selected items obtain dual presence in both hashes.  The destination
hash may already have items in it; the selected items are added to it. In order
for a structure to be usable with <tt>HASH_SELECT</tt>, it must have two or more hash
handles. (As described <a href="#multihash">here</a>, a structure can exist in many
hash tables at the same time; it must have a separate hash handle for each one).</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>user_t *users=NULL, *admins=NULL; /* two hash tables */</tt></pre>
</div></div>
<div class="literalblock">
<div class="content">
<pre><tt>typedef struct {
    int id;
    UT_hash_handle hh;  /* handle for users hash */
    UT_hash_handle ah;  /* handle for admins hash */
} user_t;</tt></pre>
</div></div>
<div class="paragraph"><p>Now suppose we have added some users, and want to select just the administrator
users who have id&#8217;s less than 1024.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>#define is_admin(x) (((user_t*)x)-&gt;id &lt; 1024)
HASH_SELECT(ah,admins,hh,users,is_admin);</tt></pre>
</div></div>
<div class="paragraph"><p>The first two parameters are the <em>destination</em> hash handle and hash table, the
second two parameters are the <em>source</em> hash handle and hash table, and the last
parameter is the <em>select condition</em>. Here we used a macro <tt>is_admin()</tt> but we
could just as well have used a function.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>int is_admin(void *userv) {
  user_t *user = (user_t*)userv;
  return (user-&gt;id &lt; 1024) ? 1 : 0;
}</tt></pre>
</div></div>
<div class="paragraph"><p>If the select condition always evaluates to true, this operation is
essentially a <em>merge</em> of the source hash into the destination hash. Of course,
the source hash remains unchanged under any use of <tt>HASH_SELECT</tt>. It only adds
items to the destination hash selectively.</p></div>
<div class="paragraph"><p>The two hash handles must differ. An example of using <tt>HASH_SELECT</tt> is included
in <tt>tests/test36.c</tt>.</p></div>
</div>
<div class="sect2">
<h3 id="hash_functions">Built-in hash functions</h3>
<div class="paragraph"><p>Internally, a hash function transforms a key into a bucket number.  You don&#8217;t
have to take any action to use the default hash function, currently Jenkin&#8217;s.</p></div>
<div class="paragraph"><p>Some programs may benefit from using another of the built-in hash functions.
There is a simple analysis utility included with uthash to help you determine
if another hash function will give you better performance.</p></div>
<div class="paragraph"><p>You can use a different hash function by compiling your program with
<tt>-DHASH_FUNCTION=HASH_xyz</tt> where <tt>xyz</tt> is one of the symbolic names listed
below. E.g.,</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>cc -DHASH_FUNCTION=HASH_BER -o program program.c</tt></pre>
</div></div>
<div class="tableblock">
<table rules="none"
width="50%"
frame="border"
cellspacing="0" cellpadding="4">
<caption class="title">Table 2. Built-in hash functions</caption>
<col width="20%" />
<col width="80%" />
<thead>
<tr>
<th align="center" valign="top">Symbol </th>
<th align="left" valign="top">   Name</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center" valign="top"><p class="table"><tt>JEN</tt></p></td>
<td align="left" valign="top"><p class="table">Jenkins (default)</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>BER</tt></p></td>
<td align="left" valign="top"><p class="table">Bernstein</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>SAX</tt></p></td>
<td align="left" valign="top"><p class="table">Shift-Add-Xor</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>OAT</tt></p></td>
<td align="left" valign="top"><p class="table">One-at-a-time</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>FNV</tt></p></td>
<td align="left" valign="top"><p class="table">Fowler/Noll/Vo</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>SFH</tt></p></td>
<td align="left" valign="top"><p class="table">Paul Hsieh</p></td>
</tr>
<tr>
<td align="center" valign="top"><p class="table"><tt>MUR</tt></p></td>
<td align="left" valign="top"><p class="table">MurmurHash v3 (see note)</p></td>
</tr>
</tbody>
</table>
</div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
<div class="title">MurmurHash</div>
<div class="paragraph"><p>A special symbol must be defined if you intend to use MurmurHash. To use it, add
<tt>-DHASH_USING_NO_STRICT_ALIASING</tt> to your <tt>CFLAGS</tt>. And, if you are using
the gcc compiler with optimization, add <tt>-fno-strict-aliasing</tt> to your <tt>CFLAGS</tt>.</p></div>
</td>
</tr></table>
</div>
<div class="sect3">
<h4 id="_which_hash_function_is_best">Which hash function is best?</h4>
<div class="paragraph"><p>You can easily determine the best hash function for your key domain. To do so,
you&#8217;ll need to run your program once in a data-collection pass, and then run
the collected data through an included analysis utility.</p></div>
<div class="paragraph"><p>First you must build the analysis utility. From the top-level directory,</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>cd tests/
make</tt></pre>
</div></div>
<div class="paragraph"><p>We&#8217;ll use <tt>test14.c</tt> to demonstrate the data-collection and analysis steps
(here using <tt>sh</tt> syntax to redirect file descriptor 3 to a file):</p></div>
<div class="listingblock">
<div class="title">Using keystats</div>
<div class="content">
<pre><tt>% cc -DHASH_EMIT_KEYS=3 -I../src -o test14 test14.c
% ./test14 3&gt;test14.keys
% ./keystats test14.keys
fcn  ideal%     #items   #buckets  dup%  fl   add_usec  find_usec  del-all usec
---  ------ ---------- ---------- -----  -- ---------- ----------  ------------
SFH   91.6%       1219        256    0%  ok         92        131            25
FNV   90.3%       1219        512    0%  ok        107         97            31
SAX   88.7%       1219        512    0%  ok        111        109            32
OAT   87.2%       1219        256    0%  ok         99        138            26
JEN   86.7%       1219        256    0%  ok         87        130            27
BER   86.2%       1219        256    0%  ok        121        129            27</tt></pre>
</div></div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">The number 3 in <tt>-DHASH_EMIT_KEYS=3</tt> is a file descriptor. Any file descriptor
that your program doesn&#8217;t use for its own purposes can be used instead of 3.
The data-collection mode enabled by <tt>-DHASH_EMIT_KEYS=x</tt> should not be used in
production code.</td>
</tr></table>
</div>
<div class="paragraph"><p>Usually, you should just pick the first hash function that is listed. Here, this
is <tt>SFH</tt>.  This is the function that provides the most even distribution for
your keys. If several have the same <tt>ideal%</tt>, then choose the fastest one
according to the <tt>find_usec</tt> column.</p></div>
</div>
<div class="sect3">
<h4 id="_keystats_column_reference">keystats column reference</h4>
<div class="dlist"><dl>
<dt class="hdlist1">
fcn
</dt>
<dd>
<p>
    symbolic name of hash function
</p>
</dd>
<dt class="hdlist1">
ideal%
</dt>
<dd>
<p>
    The percentage of items in the hash table which can be looked up within an
    ideal number of steps. (Further explained below).
</p>
</dd>
<dt class="hdlist1">
#items
</dt>
<dd>
<p>
    the number of keys that were read in from the emitted key file
</p>
</dd>
<dt class="hdlist1">
#buckets
</dt>
<dd>
<p>
    the number of buckets in the hash after all the keys were added
</p>
</dd>
<dt class="hdlist1">
dup%
</dt>
<dd>
<p>
    the percent of duplicate keys encountered in the emitted key file.
    Duplicates keys are filtered out to maintain key uniqueness. (Duplicates
    are normal.  For example, if the application adds an item to a hash,
    deletes it, then re-adds it, the key is written twice to the emitted file.)
</p>
</dd>
<dt class="hdlist1">
flags
</dt>
<dd>
<p>
    this is either <tt>ok</tt>, or <tt>nx</tt> (noexpand) if the expansion inhibited flag is
    set, described in <a href="#expansion">Expansion internals</a>.  It is not recommended
    to use a hash function that has the <tt>noexpand</tt> flag set.
</p>
</dd>
<dt class="hdlist1">
add_usec
</dt>
<dd>
<p>
    the clock time in microseconds required to add all the keys to a hash
</p>
</dd>
<dt class="hdlist1">
find_usec
</dt>
<dd>
<p>
    the clock time in microseconds required to look up every key in the hash
</p>
</dd>
<dt class="hdlist1">
del-all usec
</dt>
<dd>
<p>
    the clock time in microseconds required to delete every item in the hash
</p>
</dd>
</dl></div>
</div>
<div class="sect3">
<h4 id="ideal">ideal%</h4>
<div class="sidebarblock">
<div class="content">
<div class="title">What is ideal%?</div>
<div class="paragraph"><p>The <em>n</em> items in a hash are distributed into <em>k</em> buckets. Ideally each bucket
would contain an equal share <em>(n/k)</em> of the items. In other words, the maximum
linear position of any item in a bucket chain would be <em>n/k</em> if every bucket is
equally used. If some buckets are overused and others are underused, the
overused buckets will contain items whose linear position surpasses <em>n/k</em>.
Such items are considered non-ideal.</p></div>
<div class="paragraph"><p>As you might guess, <tt>ideal%</tt> is the percentage of ideal items in the hash. These
items have favorable linear positions in their bucket chains.  As <tt>ideal%</tt>
approaches 100%, the hash table approaches constant-time lookup performance.</p></div>
</div></div>
</div>
</div>
<div class="sect2">
<h3 id="hashscan">hashscan</h3>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">This utility is only available on Linux, and on FreeBSD (8.1 and up).</td>
</tr></table>
</div>
<div class="paragraph"><p>A utility called <tt>hashscan</tt> is included in the <tt>tests/</tt> directory. It
is built automatically when you run <tt>make</tt> in that directory. This tool
examines a running process and reports on the uthash tables that it finds in
that program&#8217;s memory. It can also save the keys from each table in a format
that can be fed into <tt>keystats</tt>.</p></div>
<div class="paragraph"><p>Here is an example of using <tt>hashscan</tt>. First ensure that it is built:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>cd tests/
make</tt></pre>
</div></div>
<div class="paragraph"><p>Since <tt>hashscan</tt> needs a running program to inspect, we&#8217;ll start up a simple
program that makes a hash table and then sleeps as our test subject:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>./test_sleep &amp;
pid: 9711</tt></pre>
</div></div>
<div class="paragraph"><p>Now that we have a test program, let&#8217;s run <tt>hashscan</tt> on it:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>./hashscan 9711
Address            ideal    items  buckets mc fl bloom/sat fcn keys saved to
------------------ ----- -------- -------- -- -- --------- --- -------------
0x862e038            81%    10000     4096 11 ok 16    14% JEN</tt></pre>
</div></div>
<div class="paragraph"><p>If we wanted to copy out all its keys for external analysis using <tt>keystats</tt>,
add the <tt>-k</tt> flag:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>./hashscan -k 9711
Address            ideal    items  buckets mc fl bloom/sat fcn keys saved to
------------------ ----- -------- -------- -- -- --------- --- -------------
0x862e038            81%    10000     4096 11 ok 16    14% JEN /tmp/9711-0.key</tt></pre>
</div></div>
<div class="paragraph"><p>Now we could run <tt>./keystats /tmp/9711-0.key</tt> to analyze which hash function
has the best characteristics on this set of keys.</p></div>
<div class="sect3">
<h4 id="_hashscan_column_reference">hashscan column reference</h4>
<div class="dlist"><dl>
<dt class="hdlist1">
Address
</dt>
<dd>
<p>
    virtual address of the hash table
</p>
</dd>
<dt class="hdlist1">
ideal
</dt>
<dd>
<p>
    The percentage of items in the table which can be looked up within an ideal
    number of steps. See <a href="#ideal">[ideal]</a> in the <tt>keystats</tt> section.
</p>
</dd>
<dt class="hdlist1">
items
</dt>
<dd>
<p>
    number of items in the hash table
</p>
</dd>
<dt class="hdlist1">
buckets
</dt>
<dd>
<p>
    number of buckets in the hash table
</p>
</dd>
<dt class="hdlist1">
mc
</dt>
<dd>
<p>
    the maximum chain length found in the hash table (uthash usually tries to
    keep fewer than 10 items in each bucket, or in some cases a multiple of 10)
</p>
</dd>
<dt class="hdlist1">
fl
</dt>
<dd>
<p>
    flags (either <tt>ok</tt>, or <tt>NX</tt> if the expansion-inhibited flag is set)
</p>
</dd>
<dt class="hdlist1">
bloom/sat
</dt>
<dd>
<p>
    if the hash table uses a Bloom filter, this is the size (as a power of two)
    of the filter (e.g. 16 means the filter is 2^16 bits in size). The second
    number is the "saturation" of the bits expressed as a percentage. The lower
    the percentage, the more potential benefit to identify cache misses quickly.
</p>
</dd>
<dt class="hdlist1">
fcn
</dt>
<dd>
<p>
    symbolic name of hash function
</p>
</dd>
<dt class="hdlist1">
keys saved to
</dt>
<dd>
<p>
    file to which keys were saved, if any
</p>
</dd>
</dl></div>
<div class="sidebarblock">
<div class="content">
<div class="title">How hashscan works</div>
<div class="paragraph"><p>When hashscan runs, it attaches itself to the target process, which suspends
the target process momentarily. During this brief suspension, it scans the
target&#8217;s virtual memory for the signature of a uthash hash table. It then
checks if a valid hash table structure accompanies the signature and reports
what it finds. When it detaches, the target process resumes running normally.
The hashscan is performed "read-only"-- the target process is not modified.
Since hashscan is analyzing a momentary snapshot of a running process, it may
return different results from one run to another.</p></div>
</div></div>
</div>
</div>
<div class="sect2">
<h3 id="expansion">Expansion internals</h3>
<div class="paragraph"><p>Internally this hash manages the number of buckets, with the goal of having
enough buckets so that each one contains only a small number of items.</p></div>
<div class="sidebarblock">
<div class="content">
<div class="title">Why does the number of buckets matter?</div>
<div class="paragraph"><p>When looking up an item by its key, this hash scans linearly through the items
in the appropriate bucket. In order for the linear scan to run in constant
time, the number of items in each bucket must be bounded. This is accomplished
by increasing the number of buckets as needed.</p></div>
</div></div>
<div class="sect3">
<h4 id="_normal_expansion">Normal expansion</h4>
<div class="paragraph"><p>This hash attempts to keep fewer than 10 items in each bucket. When an item is
added that would cause a bucket to exceed this number, the number of buckets in
the hash is doubled and the items are redistributed into the new buckets. In an
ideal world, each bucket will then contain half as many items as it did before.</p></div>
<div class="paragraph"><p>Bucket expansion occurs automatically and invisibly as needed. There is
no need for the application to know when it occurs.</p></div>
<div class="sect4">
<h5 id="_per_bucket_expansion_threshold">Per-bucket expansion threshold</h5>
<div class="paragraph"><p>Normally all buckets share the same threshold (10 items) at which point bucket
expansion is triggered. During the process of bucket expansion, uthash can
adjust this expansion-trigger threshold on a per-bucket basis if it sees that
certain buckets are over-utilized.</p></div>
<div class="paragraph"><p>When this threshold is adjusted, it goes from 10 to a multiple of 10 (for that
particular bucket).  The multiple is based on how many times greater the actual
chain length is than the ideal length. It is a practical measure to reduce
excess bucket expansion in the case where a hash function over-utilizes a few
buckets but has good overall distribution. However, if the overall distribution
gets too bad, uthash changes tactics.</p></div>
</div>
</div>
<div class="sect3">
<h4 id="_inhibited_expansion">Inhibited expansion</h4>
<div class="paragraph"><p>You usually don&#8217;t need to know or worry about this, particularly if you used
the <tt>keystats</tt> utility during development to select a good hash for your keys.</p></div>
<div class="paragraph"><p>A hash function may yield an uneven distribution of items across the buckets.
In moderation this is not a problem. Normal bucket expansion takes place as
the chain lengths grow. But when significant imbalance occurs (because the hash
function is not well suited to the key domain), bucket expansion may be
ineffective at reducing the chain lengths.</p></div>
<div class="paragraph"><p>Imagine a very bad hash function which always puts every item in bucket 0. No
matter how many times the number of buckets is doubled, the chain length of
bucket 0 stays the same. In a situation like this, the best behavior is to
stop expanding, and accept O(n) lookup performance. This is what uthash
does. It degrades gracefully if the hash function is ill-suited to the keys.</p></div>
<div class="paragraph"><p>If two consecutive bucket expansions yield <tt>ideal%</tt> values below 50%, uthash
inhibits expansion for that hash table.  Once set, the <em>bucket expansion
inhibited</em> flag remains in effect as long as the hash has items in it.
Inhibited expansion may cause <tt>HASH_FIND</tt> to exhibit worse than constant-time
performance.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_hooks">Hooks</h3>
<div class="paragraph"><p>You don&#8217;t need to use these hooks- they are only here if you want to modify
the behavior of uthash.  Hooks can be used to change how uthash allocates
memory, and to run code in response to certain internal events.</p></div>
<div class="sect3">
<h4 id="_malloc_free">malloc/free</h4>
<div class="paragraph"><p>By default this hash implementation uses <tt>malloc</tt> and <tt>free</tt> to manage memory.
If your application uses its own custom allocator, this hash can use them too.</p></div>
<div class="listingblock">
<div class="title">Specifying alternate memory management functions</div>
<div class="content">
<pre><tt>#include "uthash.h"

/* undefine the defaults */
#undef uthash_malloc
#undef uthash_free

/* re-define, specifying alternate functions */
#define uthash_malloc(sz) my_malloc(sz)
#define uthash_free(ptr,sz) my_free(ptr)

...</tt></pre>
</div></div>
<div class="paragraph"><p>Notice that <tt>uthash_free</tt> receives two parameters. The <tt>sz</tt> parameter is for
convenience on embedded platforms that manage their own memory.</p></div>
</div>
<div class="sect3">
<h4 id="_out_of_memory">Out of memory</h4>
<div class="paragraph"><p>If memory allocation fails (i.e., the malloc function returned <tt>NULL</tt>), the
default behavior is to terminate the process by calling <tt>exit(-1)</tt>. This can
be modified by re-defining the <tt>uthash_fatal</tt> macro.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>#undef uthash_fatal
#define uthash_fatal(msg) my_fatal_function(msg);</tt></pre>
</div></div>
<div class="paragraph"><p>The fatal function should terminate the process or <tt>longjmp</tt> back to a safe
place. Uthash does not support "returning a failure" if memory cannot be
allocated.</p></div>
</div>
<div class="sect3">
<h4 id="_internal_events">Internal events</h4>
<div class="paragraph"><p>There is no need for the application to set these hooks or take action in
response to these events. They are mainly for diagnostic purposes.</p></div>
<div class="paragraph"><p>These two hooks are "notification" hooks which get executed if uthash is
expanding buckets, or setting the <em>bucket expansion inhibited</em> flag. Normally
both of these hooks are undefined and thus compile away to nothing.</p></div>
<div class="sect4">
<h5 id="_expansion">Expansion</h5>
<div class="paragraph"><p>There is a hook for the bucket expansion event.</p></div>
<div class="listingblock">
<div class="title">Bucket expansion hook</div>
<div class="content">
<pre><tt>#include "uthash.h"

#undef uthash_expand_fyi
#define uthash_expand_fyi(tbl) printf("expanded to %d buckets\n", tbl-&gt;num_buckets)

...</tt></pre>
</div></div>
</div>
<div class="sect4">
<h5 id="_expansion_inhibition">Expansion-inhibition</h5>
<div class="paragraph"><p>This hook can be defined to code to execute in the event that uthash decides to
set the <em>bucket expansion inhibited</em> flag.</p></div>
<div class="listingblock">
<div class="title">Bucket expansion inhibited hook</div>
<div class="content">
<pre><tt>#include "uthash.h"

#undef uthash_noexpand_fyi
#define uthash_noexpand_fyi printf("warning: bucket expansion inhibited\n");

...</tt></pre>
</div></div>
</div>
</div>
</div>
<div class="sect2">
<h3 id="_debug_mode">Debug mode</h3>
<div class="paragraph"><p>If a program that uses this hash is compiled with <tt>-DHASH_DEBUG=1</tt>, a special
internal consistency-checking mode is activated.  In this mode, the integrity
of the whole hash is checked following every add or delete operation.  This is
for debugging the uthash software only, not for use in production code.</p></div>
<div class="paragraph"><p>In the <tt>tests/</tt> directory, running <tt>make debug</tt> will run all the tests in
this mode.</p></div>
<div class="paragraph"><p>In this mode, any internal errors in the hash data structure will cause a
message to be printed to <tt>stderr</tt> and the program to exit.</p></div>
<div class="paragraph"><p>The <tt>UT_hash_handle</tt> data structure includes <tt>next</tt>, <tt>prev</tt>, <tt>hh_next</tt> and
<tt>hh_prev</tt> fields.  The former two fields determine the "application" ordering
(that is, insertion order-- the order the items were added).  The latter two
fields determine the "bucket chain" order.  These link the <tt>UT_hash_handles</tt>
together in a doubly-linked list that is a bucket chain.</p></div>
<div class="paragraph"><p>Checks performed in <tt>-DHASH_DEBUG=1</tt> mode:</p></div>
<div class="ulist"><ul>
<li>
<p>
the hash is walked in its entirety twice: once in <em>bucket</em> order and a
  second time in <em>application</em> order
</p>
</li>
<li>
<p>
the total number of items encountered in both walks is checked against the
  stored number
</p>
</li>
<li>
<p>
during the walk in <em>bucket</em> order, each item&#8217;s <tt>hh_prev</tt> pointer is compared
  for equality with the last visited item
</p>
</li>
<li>
<p>
during the walk in <em>application</em> order, each item&#8217;s <tt>prev</tt> pointer is compared
  for equality with the last visited item
</p>
</li>
</ul></div>
<div class="sidebarblock">
<div class="content">
<div class="title">Macro debugging:</div>
<div class="paragraph"><p>Sometimes it&#8217;s difficult to interpret a compiler warning on a line which
contains a macro call.  In the case of uthash, one macro can expand to dozens of
lines. In this case, it is helpful to expand the macros and then recompile.
By doing so, the warning message will refer to the exact line within the macro.</p></div>
<div class="paragraph"><p>Here is an example of how to expand the macros and then recompile. This uses the
<tt>test1.c</tt> program in the <tt>tests/</tt> subdirectory.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>gcc -E -I../src test1.c &gt; /tmp/a.c
egrep -v '^#' /tmp/a.c &gt; /tmp/b.c
indent /tmp/b.c
gcc -o /tmp/b /tmp/b.c</tt></pre>
</div></div>
<div class="paragraph"><p>The last line compiles the original program (test1.c) with all macros expanded.
If there was a warning, the referenced line number can be checked in <tt>/tmp/b.c</tt>.</p></div>
</div></div>
</div>
<div class="sect2">
<h3 id="_thread_safety">Thread safety</h3>
<div class="paragraph"><p>You can use uthash in a threaded program. But you must do the locking. Use a
read-write lock to protect against concurrent writes. It is ok to have
concurrent readers (since uthash 1.5).</p></div>
<div class="paragraph"><p>For example using pthreads you can create an rwlock like this:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>pthread_rwlock_t lock;
if (pthread_rwlock_init(&amp;lock,NULL) != 0) fatal("can't create rwlock");</tt></pre>
</div></div>
<div class="paragraph"><p>Then, readers must acquire the read lock before doing any <tt>HASH_FIND</tt> calls or
before iterating over the hash elements:</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>if (pthread_rwlock_rdlock(&amp;lock) != 0) fatal("can't get rdlock");
HASH_FIND_INT(elts, &amp;i, e);
pthread_rwlock_unlock(&amp;lock);</tt></pre>
</div></div>
<div class="paragraph"><p>Writers must acquire the exclusive write lock before doing any update. Add,
delete, and sort are all updates that must be locked.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>if (pthread_rwlock_wrlock(&amp;lock) != 0) fatal("can't get wrlock");
HASH_DEL(elts, e);
pthread_rwlock_unlock(&amp;lock);</tt></pre>
</div></div>
<div class="paragraph"><p>If you prefer, you can use a mutex instead of a read-write lock, but this will
reduce reader concurrency to a single thread at a time.</p></div>
<div class="paragraph"><p>An example program using uthash with a read-write lock is included in
<tt>tests/threads/test1.c</tt>.</p></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="Macro_reference">Macro reference</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_convenience_macros">Convenience macros</h3>
<div class="paragraph"><p>The convenience macros do the same thing as the generalized macros, but
require fewer arguments.</p></div>
<div class="paragraph"><p>In order to use the convenience macros,</p></div>
<div class="olist arabic"><ol class="arabic">
<li>
<p>
the structure&#8217;s <tt>UT_hash_handle</tt> field must be named <tt>hh</tt>, and
</p>
</li>
<li>
<p>
for add or find, the key field must be of type <tt>int</tt> or <tt>char[]</tt> or pointer
</p>
</li>
</ol></div>
<div class="tableblock">
<table rules="none"
width="90%"
frame="border"
cellspacing="0" cellpadding="4">
<caption class="title">Table 3. Convenience macros</caption>
<col width="25%" />
<col width="75%" />
<thead>
<tr>
<th align="left" valign="top">macro            </th>
<th align="left" valign="top"> arguments</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ADD_INT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, keyfield_name, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_REPLACE_INT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, keyfiled_name, item_ptr,replaced_item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_FIND_INT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, key_ptr, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ADD_STR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, keyfield_name, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_REPLACE_STR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head,keyfield_name, item_ptr, replaced_item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_FIND_STR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, key_ptr, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ADD_PTR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, keyfield_name, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_REPLACE_PTR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, keyfield_name, item_ptr, replaced_item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_FIND_PTR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, key_ptr, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_DEL</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_SORT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head, cmp)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_COUNT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(head)</tt></p></td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="sect2">
<h3 id="_general_macros">General macros</h3>
<div class="paragraph"><p>These macros add, find, delete and sort the items in a hash.  You need to
use the general macros if your <tt>UT_hash_handle</tt> is named something other
than <tt>hh</tt>, or if your key&#8217;s data type isn&#8217;t <tt>int</tt> or <tt>char[]</tt>.</p></div>
<div class="tableblock">
<table rules="none"
width="90%"
frame="border"
cellspacing="0" cellpadding="4">
<caption class="title">Table 4. General macros</caption>
<col width="25%" />
<col width="75%" />
<thead>
<tr>
<th align="left" valign="top">macro          </th>
<th align="left" valign="top"> arguments</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ADD</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, keyfield_name, key_len, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ADD_KEYPTR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, key_ptr, key_len, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_REPLACE</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, keyfield_name, key_len, item_ptr, replaced_item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_FIND</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, key_ptr, key_len, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_DELETE</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_SRT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, cmp)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_CNT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_CLEAR</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_SELECT</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(dst_hh_name, dst_head, src_hh_name, src_head, condition)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_ITER</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head, item_ptr, tmp_item_ptr)</tt></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><tt>HASH_OVERHEAD</tt></p></td>
<td align="left" valign="top"><p class="table"><tt>(hh_name, head)</tt></p></td>
</tr>
</tbody>
</table>
</div>
<div class="admonitionblock">
<table><tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content"><tt>HASH_ADD_KEYPTR</tt> is used when the structure contains a pointer to the
key, rather than the key itself.</td>
</tr></table>
</div>
<div class="sect3">
<h4 id="_argument_descriptions">Argument descriptions</h4>
<div class="dlist"><dl>
<dt class="hdlist1">
hh_name
</dt>
<dd>
<p>
    name of the <tt>UT_hash_handle</tt> field in the structure. Conventionally called
    <tt>hh</tt>.
</p>
</dd>
<dt class="hdlist1">
head
</dt>
<dd>
<p>
    the structure pointer variable which acts as the "head" of the hash. So
    named because it initially points to the first item that is added to the hash.
</p>
</dd>
<dt class="hdlist1">
keyfield_name
</dt>
<dd>
<p>
    the name of the key field in the structure. (In the case of a multi-field
    key, this is the first field of the key). If you&#8217;re new to macros, it
    might seem strange to pass the name of a field as a parameter. See
    <a href="#validc">note</a>.
</p>
</dd>
<dt class="hdlist1">
key_len
</dt>
<dd>
<p>
    the length of the key field in bytes. E.g. for an integer key, this is
    <tt>sizeof(int)</tt>, while for a string key it&#8217;s <tt>strlen(key)</tt>. (For a
    multi-field key, see the notes in this guide on calculating key length).
</p>
</dd>
<dt class="hdlist1">
key_ptr
</dt>
<dd>
<p>
    for <tt>HASH_FIND</tt>, this is a pointer to the key to look up in the hash
    (since it&#8217;s a pointer, you can&#8217;t directly pass a literal value here). For
    <tt>HASH_ADD_KEYPTR</tt>, this is the address of the key of the item being added.
</p>
</dd>
<dt class="hdlist1">
item_ptr
</dt>
<dd>
<p>
    pointer to the structure being added, deleted, or looked up, or the current
    pointer during iteration. This is an input parameter for <tt>HASH_ADD</tt> and
    <tt>HASH_DELETE</tt> macros, and an output parameter for <tt>HASH_FIND</tt> and
    <tt>HASH_ITER</tt>. (When using <tt>HASH_ITER</tt> to iterate, <tt>tmp_item_ptr</tt>
    is another variable of the same type as <tt>item_ptr</tt>, used internally).
</p>
</dd>
<dt class="hdlist1">
replaced_item_ptr
</dt>
<dd>
<p>
    used in HASH_REPLACE macros. This is an output parameter that is set to point
    to the replaced item (if no item is replaced it is set to NULL).
</p>
</dd>
<dt class="hdlist1">
cmp
</dt>
<dd>
<p>
    pointer to comparison function which accepts two arguments (pointers to
    items to compare) and returns an int specifying whether the first item
    should sort before, equal to, or after the second item (like <tt>strcmp</tt>).
</p>
</dd>
<dt class="hdlist1">
condition
</dt>
<dd>
<p>
    a function or macro which accepts a single argument-- a void pointer to a
    structure, which needs to be cast to the appropriate structure type. The
    function or macro should return (or evaluate to) a non-zero value if the
    structure should be "selected" for addition to the destination hash.
</p>
</dd>
</dl></div>
</div>
</div>
</div>
</div>
</div>
<div id="footnotes"><hr /></div>
<div id="footer">
<div id="footer-text">
Version 1.9.8<br />
Last updated 2013-04-15 23:26:30 EDT
</div>
</div>
</body>
</html>
